#include "InterviewLink.h"
#include "LinkList.h"
#define TEST_HEADER printf("\n******************************%s**********************\n",__FUNCTION__)


void TestReverPrintLinkList()
{
   TEST_HEADER;
   LinkNode *head;
    LinkListInit(&head);
    LinkListPushFront(&head,'g');
    LinkListPushFront(&head,'f');
    LinkListPushFront(&head,'e');
    LinkListPushFront(&head,'d');
    LinkListPushFront(&head,'c');
    LinkListPushFront(&head,'b');
    LinkListPushFront(&head,'a');
    PrintListChar(head,"头插7个元素");
    printf("逆序打印单链表\n");
    ReversePrintLinkList(head);
}
void TestInsertLinkList()
{
   TEST_HEADER;
   LinkNode *head;
    LinkListInit(&head);
    LinkListPushFront(&head,'g');
    LinkListPushFront(&head,'f');
    LinkNode *pos_e=LinkListPushFront(&head,'e');
    LinkListPushFront(&head,'d');
    LinkNode *pos_c=LinkListPushFront(&head,'c');
    LinkListPushFront(&head,'b');
    LinkNode *pos_a=LinkListPushFront(&head,'a');
    PrintListChar(head,"头插7个元素");
    InsertFrontLinkList(&head,pos_c,'z');
    PrintListChar(head,"在c之前插入z");
    InsertFrontLinkList(&head,pos_e,'m');
    PrintListChar(head,"在e之前插入m");
    InsertFrontLinkList(&head,pos_a,'n');
    PrintListChar(head,"在a之前插入n");
}

void TestLinkListReverse_1()
{
   TEST_HEADER;
   LinkNode *head;
    LinkListInit(&head);
    LinkListPushFront(&head,'g');
    LinkListPushFront(&head,'f');
    LinkListPushFront(&head,'e');
    LinkListPushFront(&head,'d');
    LinkListPushFront(&head,'c');
    LinkListPushFront(&head,'b');
    LinkListPushFront(&head,'a');
    PrintListChar(head,"头插7个元素");
    LinkListReverse_1(&head);
    PrintListChar(head,"将链表逆置后");
}
void TestLinkListReverse_2()
{
   TEST_HEADER;
   LinkNode *head;
    LinkListInit(&head);
    LinkListPushFront(&head,'g');
    LinkListPushFront(&head,'f');
    LinkListPushFront(&head,'e');
    LinkListPushFront(&head,'d');
    LinkListPushFront(&head,'c');
    LinkListPushFront(&head,'b');
    LinkListPushFront(&head,'a');
    PrintListChar(head,"头插7个元素");
    LinkListReverse_2(&head);
    PrintListChar(head,"将链表进行逆置后");
}
void TestLinkListBubbleSort()
{
    TEST_HEADER;
    LinkNode *head;
    LinkListInit(&head);
    LinkListPushFront(&head,'a');
    LinkListPushFront(&head,'f');
    LinkListPushFront(&head,'c');
    LinkListPushFront(&head,'b');
    LinkListPushFront(&head,'e');
    LinkListPushFront(&head,'g');
    LinkListPushFront(&head,'d');
    PrintListChar(head,"头插7个元素");
    LinkListBubbleSort(head);
    PrintListChar(head,"进行冒泡排序后");
}
void TestLinkListMrege()
{
    TEST_HEADER;
    LinkNode *head_1;
    LinkNode *head_2;
    LinkListInit(&head_1);
    LinkListInit(&head_2);
    LinkListPushFront(&head_1,'h');
    LinkListPushFront(&head_1,'g');
    LinkListPushFront(&head_1,'f');
    LinkListPushFront(&head_1,'e');

    LinkListPushFront(&head_2,'d');
    LinkListPushFront(&head_2,'c');
    LinkListPushFront(&head_2,'b');
    LinkListPushFront(&head_2,'a');
    PrintListChar(head_1,"头插4个元素");
    PrintListChar(head_2,"头插4个元素");
    LinkNode *head=LinkListMerge(head_1,head_2);
    PrintListChar(head,"将两个有序链表进行归并后");
}
void TestFindLastKNode()
{
    TEST_HEADER;
    LinkNode *head;
    LinkListInit(&head);
    LinkNode *pos_g=LinkListPushFront(&head,'g');
    LinkListPushFront(&head,'f');
    LinkNode *pos_e=LinkListPushFront(&head,'e');
    LinkListPushFront(&head,'d');
    LinkListPushFront(&head,'c');
    LinkListPushFront(&head,'b');
    LinkNode *pos_a= LinkListPushFront(&head,'a');
    PrintListChar(head,"进行插入7个元素");
    LinkNode *ret_1=LinkListFindLastKNode(head,7);
    printf("查找倒数第7个节点，ret_1 expect [%c:%p],actual [%c:%p]\n",pos_a->data,pos_a,ret_1->data,ret_1);
    LinkNode *ret_2=LinkListFindLastKNode(head,3);
    printf("查找倒数第7个节点，ret_1 expect [%c:%p],actual [%c:%p]\n",pos_e->data,pos_e,ret_2->data,ret_2);
    LinkNode *ret_3=LinkListFindLastKNode(head,1);
    printf("查找倒数第7个节点，ret_1 expect [%c:%p],actual [%c:%p]\n",pos_g->data,pos_g,ret_3->data,ret_3);
    LinkNode *ret_4=LinkListFindLastKNode(head,8);
    printf("对非法位置进行查找，ret_4 expect NULL,actual %p\n",ret_4);
}
void TestEraseLastKNode()
{
    TEST_HEADER;
    LinkNode *head;
    LinkListInit(&head);
    LinkListPushFront(&head,'g');
    LinkListPushFront(&head,'f');
    LinkListPushFront(&head,'e');
    LinkListPushFront(&head,'d');
    LinkListPushFront(&head,'c');
    LinkListPushFront(&head,'b');
    LinkListPushFront(&head,'a');
    PrintListChar(head,"进行插入7个元素");
    LinkListEraseLastKNode(&head,7);
    PrintListChar(head,"删除倒数第7个元素后");
    LinkListEraseLastKNode(&head,3);
    PrintListChar(head,"删除倒数第3个元素后");
    LinkListEraseLastKNode(&head,1);
    PrintListChar(head,"删除倒数第1个元素后");
}
void TestLinkListHasCycle()
{
    TEST_HEADER;
    LinkNode *head;
    LinkListInit(&head);
    LinkNode *pos_g=LinkListPushFront(&head,'g');
    LinkListPushFront(&head,'f');
    LinkNode *pos_e=LinkListPushFront(&head,'e');
    LinkListPushFront(&head,'d');
    LinkListPushFront(&head,'c');
    LinkListPushFront(&head,'b');
    LinkNode *pos_a= LinkListPushFront(&head,'a');
    PrintListChar(head,"进行插入7个元素");
    int ret=0;
    ret=LinkListHasCycle(head);
    printf("对一个不带环的链表进行判断是否带环, ret expect 0,actual %d\n",ret);
    pos_g->next=pos_e;
    ret=LinkListHasCycle(head);
    printf("对带环的链表进行判断, ret expect 1,actual %d\n",ret);
    pos_g->next=pos_a;
    ret=LinkListHasCycle(head);
    printf("对带环的链表进行判断, ret expect 1,actual %d\n",ret);
}
void TestLinkListGetCycleSize()
{
    TEST_HEADER;
    LinkNode *head;
    LinkListInit(&head);
    LinkNode *pos_g=LinkListPushFront(&head,'g');
    LinkListPushFront(&head,'f');
    LinkNode *pos_e=LinkListPushFront(&head,'e');
    LinkListPushFront(&head,'d');
    LinkListPushFront(&head,'c');
    LinkListPushFront(&head,'b');
    LinkNode *pos_a= LinkListPushFront(&head,'a');
    PrintListChar(head,"进行插入7个元素");
    size_t size=0;
    size=LinkListGetCycleSize(head);
    printf("对不带环链表进行求环的长度：size expect 0,actual %lu\n",size);
    pos_g->next=pos_e;
    size=LinkListGetCycleSize(head);
    printf("求环的长度：size expect 3,actual %lu\n",size);
    pos_g->next=pos_a;
    size=LinkListGetCycleSize(head);
    printf("求环的长度：size expect 7,actual %lu\n",size);
}
void TestLinkListGetCycleEntry()
{
    TEST_HEADER;
    LinkNode *head;
    LinkListInit(&head);
    LinkNode *pos_g=LinkListPushFront(&head,'g');
    LinkListPushFront(&head,'f');
    LinkNode *pos_e=LinkListPushFront(&head,'e');
    LinkListPushFront(&head,'d');
    LinkListPushFront(&head,'c');
    LinkListPushFront(&head,'b');
    LinkNode *pos_a= LinkListPushFront(&head,'a');
    PrintListChar(head,"进行插入7个元素");
    LinkNode *entry=NULL;
    entry=LinkListGetCycleEntry(head);
    printf("对不带还的链表进行求入口：entry expect NULL,actual %p\n",entry);
    pos_g->next=pos_e;
    entry=LinkListGetCycleEntry(head);
    printf("进行求入口：entry expect %p,actual %p\n",pos_e,entry);
    pos_g->next=pos_a;
    entry=LinkListGetCycleEntry(head);
    printf("进行求入口：entry expect %p,actual %p\n",pos_a,entry);
}
void TestLinkListHasCrosses()
{
    TEST_HEADER;
    LinkNode *head_1;
    LinkListInit(&head_1);
    LinkNode *pos_g=LinkListPushFront(&head_1,'g');
    LinkListPushFront(&head_1,'f');
    LinkListPushFront(&head_1,'e');
    LinkListPushFront(&head_1,'d');
    LinkListPushFront(&head_1,'c');
    LinkListPushFront(&head_1,'b');
    LinkListPushFront(&head_1,'a');
    PrintListChar(head_1,"进行插入7个元素");
    LinkNode *head_2;
    LinkListInit(&head_2);
    LinkNode *pos_h=LinkListPushFront(&head_2,'h');
    LinkListPushFront(&head_2,'o');
    LinkNode *pos_k=LinkListPushFront(&head_2,'k');
    LinkListPushFront(&head_2,'m');
    LinkListPushFront(&head_2,'n');
    LinkListPushFront(&head_2,'p');
    LinkNode *pos_q= LinkListPushFront(&head_2,'q');
    PrintListChar(head_2,"进行插入7个元素");
    LinkNode *ret=NULL;
    ret=LinkListHasCrosses(head_1,head_2);
    printf("对不相交的链表求交点：ret expetc NULL,actual %p\n",ret);
    pos_g->next=pos_h;
    ret=LinkListHasCrosses(head_1,head_2);
    printf("链表求交点：ret expetc %p,actual %p\n",pos_h,ret);
    pos_g->next=pos_k;
    ret=LinkListHasCrosses(head_1,head_2);
    printf("链表求交点：ret expetc %p,actual %p\n",pos_k,ret);
    pos_g->next=pos_q;
    ret=LinkListHasCrosses(head_1,head_2);
    printf("链表求交点：ret expetc %p,actual %p\n",pos_q,ret);
    pos_g->next=pos_h;
}
void TestLinkListHasCrossesWithCycle()
{
    TEST_HEADER;
    LinkNode *head_1;
    LinkListInit(&head_1);
    LinkNode *pos_g=LinkListPushFront(&head_1,'g');
    LinkNode *pos_f=LinkListPushFront(&head_1,'f');
    LinkListPushFront(&head_1,'e');
    LinkNode *pos_d=LinkListPushFront(&head_1,'d');
    LinkListPushFront(&head_1,'c');
    LinkListPushFront(&head_1,'b');
    LinkNode *pos_a=LinkListPushFront(&head_1,'a');
    PrintListChar(head_1,"进行插入7个元素");
    LinkNode *head_2;
    LinkListInit(&head_2);
    LinkNode *pos_h=LinkListPushFront(&head_2,'h');
    LinkListPushFront(&head_2,'o');
    LinkListPushFront(&head_2,'k');
    LinkListPushFront(&head_2,'m');
    LinkListPushFront(&head_2,'n');
    LinkListPushFront(&head_2,'p');
    LinkNode *pos_q= LinkListPushFront(&head_2,'q');
    PrintListChar(head_2,"进行插入7个元素");
    int ret=0;
    ret=LinkListHasCrossesWithCycle(head_1,head_2);
    printf("对不带环不相交的链表求交点：ret expetc 0,actual %d\n",ret);
    pos_g->next=pos_h;
    ret=LinkListHasCrossesWithCycle(head_1,head_2);
    printf("对不带环相交链表求交点：ret expetc 1,actual %d\n",ret);
    pos_g->next=pos_d;
    ret=LinkListHasCrossesWithCycle(head_1,head_2);
    printf("对一个带环一个不带环的链表求交点：ret expetc 0,actual %d\n",ret);
    pos_h->next=pos_d;
    ret=LinkListHasCrossesWithCycle(head_1,head_2);
    printf("对交点在环外的链表求交点：ret expetc 1,actual %d\n",ret);
    pos_h->next=pos_f;
    ret=LinkListHasCrossesWithCycle(head_1,head_2);
    printf("对交点在环上的链表求交点：ret expetc 1,actual %d\n",ret);
    pos_g->next=pos_a;
    pos_h->next=pos_q;
    ret=LinkListHasCrossesWithCycle(head_1,head_2);
    printf("对两个都带环不相交的链表求交点：ret expetc 0,actual %d\n",ret);
}
int main()
{
    TestReverPrintLinkList();
    TestInsertLinkList();
    TestLinkListReverse_1();
    TestLinkListReverse_2();
    TestLinkListBubbleSort();
    TestLinkListMrege();
    TestFindLastKNode();
    TestEraseLastKNode();
    TestLinkListHasCycle();
    TestLinkListGetCycleSize();
    TestLinkListGetCycleEntry();
    TestLinkListHasCrosses();
    TestLinkListHasCrossesWithCycle();
    return 0;
}
